#
# @lc app=leetcode.cn id=2438 lang=python3
#
# [2438] 二的幂数组中查询范围内的乘积
#

# @lc code=start
from typing import List


class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        mod = 1_0000_00007
        #先构造power数组
        power = []
        while n:
            lowbit = n & -n  # 取最低位的1
            n ^= lowbit  # 去掉最低位的1
            power.append(lowbit)
        s = [1] * (len(power) + 1)
        for i,x in enumerate(power):
            s[i+1] = s[i] * x
        return [(s[r+1] // s[l])%mod for l,r in queries]
# @lc code=end

